
// 300.最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 使用贪心对动态规划进行优化
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        
        auto check = [&](int tar)           // 找到第一个比tar位置 大或等于 的位置
        {
            int l = -1 , r = ret.size();
            while(l + 1 < r){
                int mid = (l + r)/2;
                if(ret[mid] >= tar) r = mid; 
                else l = mid;
            }
            return r;
        };

        for(int i = 1 ;i < n ; i++)
        {
            if(nums[i] > ret.back()) ret.push_back(nums[i]);
            else
            {
                int pos = check(nums[i]);
                ret[pos] = nums[i];
            }
        }
        return ret.size();
    }
};